package com.lishem.carl._10dp;

/**
 *
 * https://leetcode.cn/problems/ones-and-zeroes/description/
 * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
 *
 * 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
 *
 * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
 *
 * 示例 1：
 *
 * strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
 *
 * dp数组含义：   dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
 *
 * 递推公式：                   取当前值  与 不取当前值的最大容量
 *
 *               dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
 */
public class _12LetCode474_一和零 {


    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        // 遍历物品
        for (String str : strs) {
            int mi = 0;
            int ni = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '0') {
                    mi++;
                } else {
                    ni++;
                }
            }
            // 遍历背包
            for (int i = m; i >= mi; i--) {
                for (int j = n; j >= ni; j--) {
                    dp[i][j] = Math.max(dp[i - mi][j - ni] + 1, dp[i][j]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        _12LetCode474_一和零 sol = new _12LetCode474_一和零();
        String[] strs = {"10", "0001", "111001", "1", "0"};
        System.out.println(sol.findMaxForm(strs, 5, 3));

        String[] strs1 = {"10", "0", "1"};
        System.out.println(sol.findMaxForm(strs1, 1, 1));

        System.out.println(sol.findMaxForm(strs, 3, 2));
    }
}
